package math;

/*
 * POJ3532
 */
/**
 * O(n*m^2)
 * 
 * @author yinzichen
 * 
 */
public class GaussDouble {
	/**
	 * @param a
	 *            a[n][m+1],
	 * @param n
	 *            number of equations
	 * @param m
	 *            number of variables
	 * @return variables' solution
	 */
	static double[] gauss(double a[][], int n, int m) {
		int p = -1, q = 0, i, j, max;
		double e = 1e-5, tmp;
		while (++p < m) {
			for (i = q; i < n; i++) {
				if (Math.abs(a[i][p]) > e)
					break;
			}
			if (i == n)
				continue;
			max = i++;
			for (; i < n; i++)
				if (Math.abs(a[max][p]) < Math.abs(a[i][p]))
					max = i;
			for (i = 0; i <= m; i++) {
				tmp = a[q][i];
				a[q][i] = a[max][i];
				a[max][i] = tmp;
			}
			for (i = 0; i < n; i++)
				if (i != q) {
					tmp = a[i][p];
					for (j = 0; j <= m; j++) {
						a[i][j] = a[i][j] - a[q][j] * tmp / a[q][p];
					}
				}
			q++;
		}
		double[] x = new double[m];
		j = 0;
		for (i = 0; i < m; i++) {
			while (j < m && Math.abs(a[i][j]) < e)
				j++;
			if (j >= m)
				break;
			x[j] = a[i][m] / a[i][j];
		}
		return x;
	}

	public static void main(String[] args) {
		double[][] in = new double[][] { { 1, 2, 3 }, { 2, 2, 3 }, { 1, 3, 3 } };
		double[] x = GaussDouble.gauss(in, 2, 2);
		for (double y : x)
			System.out.println(y);
	}
}